<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
    <head>
        <title>RVM : Building a Hybrid Collector</title>
	    <link rel="stylesheet" href="styles/site.css" type="text/css" />
        <META http-equiv="Content-Type" content="text/html; charset=UTF-8">	    
    </head>

    <body>
	    <table class="pagecontent" border="0" cellpadding="0" cellspacing="0" width="100%" bgcolor="#ffffff">
		    <tr>
			    <td valign="top" class="pagebody">
				    <div class="pageheader">
					    <span class="pagetitle">
                            RVM : Building a Hybrid Collector
                                                    </span>
				    </div>
				    <div class="pagesubheading">
					    This page last changed on Mar 31, 2009 by <font color="#0050B2">steveblackburn</font>.
				    </div>

				    <p>Extend the Tutorial plan to create a "copy-MS" collector, which allocates into a copying nursery and at collection time, copies nursery survivors into a mark-sweep space. This plan does not require a write barrier (it is not strictly generational, as it will collect the whole heap each time the heap is full). Later we will extended it with a write barrier, allowing the nursery to be collected in isolation. Such a collector would be a generational mark-sweep collector, similar to GenMS. </p>

<h5><a name="BuildingaHybridCollector-AddaCopyingNursery"></a>Add a Copying Nursery</h5>

<ol>
	<li>In <tt>TutorialConstraints</tt>, make the following changes:
	<ol>
		<li>Override the <tt>movesObjects()</tt> method to return <tt>true</tt>, reﬂecting that we are now building a copying collector:
<div class="code panel" style="border-width: 1px;"><div class="codeContent panelContent">
<pre class="code-java">
@Override
<span class="code-keyword">public</span> <span class="code-object">boolean</span> movesObjects() { <span class="code-keyword">return</span> <span class="code-keyword">true</span>; }
</pre>
</div></div></li>
		<li>Remove the restriction on default alloc bytes (since default allocation will now go to a bump-pointed space).  To do this, remove the override of <tt>maxNonLOSDefaultAllocBytes()</tt>.</li>
		<li>Add a restriction on the maximum size that may be copied into the (default) non-LOS mature space:
<div class="code panel" style="border-width: 1px;"><div class="codeContent panelContent">
<pre class="code-java">
@Override
<span class="code-keyword">public</span> <span class="code-object">int</span> maxNonLOSCopyBytes() { <span class="code-keyword">return</span> SegregatedFreeListSpace.MAX_FREELIST_OBJECT_BYTES;}
</pre>
</div></div></li>
	</ol>
	</li>
	<li>In <tt>Tutorial</tt>, add a nursery space:
	<ol>
		<li>Create a new space, <tt>nurserySpace</tt>, of type <tt>CopySpace</tt>. The new space will initially be a <em>from-space</em>, so provide <tt>false</tt> as the third argument. Initialize the space with a <em>contiguous</em> virtual memory region consuming 0.15 of the heap by passing "<tt>0.15</tt>" and "<tt>true</tt>" as arguments to the constructor of <tt>VMRequest</tt> (more on this later).  Create and initialize a new integer constant to hold the descriptor for this new space:
<div class="code panel" style="border-width: 1px;"><div class="codeContent panelContent">
<pre class="code-java">
<span class="code-keyword">public</span> <span class="code-keyword">static</span> <span class="code-keyword">final</span> CopySpace nurserySpace = <span class="code-keyword">new</span> CopySpace(<span class="code-quote">"nursery"</span>, DEFAULT_POLL_FREQUENCY, <span class="code-keyword">false</span>, VMRequest.create(0.15f, <span class="code-keyword">true</span>));
<span class="code-keyword">public</span> <span class="code-keyword">static</span> <span class="code-keyword">final</span> <span class="code-object">int</span> NURSERY = nurserySpace.getDescriptor();
</pre>
</div></div></li>
		<li>Add the necessary import statements</li>
		<li>Add <tt>nurserySpace</tt> to the <tt>PREPARE</tt> and <tt>RELEASE</tt> phases of <tt>collectionPhase()</tt>, prior to the existing calls to <tt>msTrace</tt>.  Pass <tt>true</tt> to <tt>nurserySpace.prepare()</tt> indicating that the nursery is a <em>from-space</em> during collection.</li>
		<li>Fix accounting so that <tt>Tutorial</tt> accounts for space consumed by <tt>nurserySpace</tt>:
		<ol>
			<li>Add <tt>nurserySpace</tt> to the equation in <tt>getPagesUsed()</tt>,</li>
		</ol>
		</li>
		<li>Since initial allocation will be into a copying space, we need to account for copy reserve:
		<ol>
			<li>Change <tt>getPagesRequired()</tt>, replacing <tt>msSpace.requiredPages()</tt> with <tt>(nurserySpace.requiredPages() * 2)</tt></li>
			<li>Add a method to override <tt>getCollectionReserve()</tt> which returns <tt>nurserySpace.reservedPages() + super.getCollectionReserve()</tt>,</li>
			<li>Add a method to override <tt>getPagesAvail()</tt>, returning <tt>super.getPagesAvail()/2</tt>,</li>
		</ol>
		</li>
	</ol>
	</li>
</ol>


<h5><a name="BuildingaHybridCollector-Addnurseryallocation"></a>Add nursery allocation</h5>

<p>In <tt>TutorialMutator</tt>, replace the free-list allocator (<tt>MarkSweepLocal</tt>) with add a nursery allocator.  Add an instance of <tt>CopyLocal</tt>, calling it <tt>nursery</tt>.   The constructor argument should be <tt>Tutorial.nurserySpace</tt>:</p>
<ol>
	<li>change <tt>alloc()</tt> to use <tt>nursery.alloc()</tt> rather than <tt>ms.alloc()</tt>.</li>
	<li>remove the call to <tt>msSpace.postAlloc()</tt> from <tt>postAlloc()</tt> since there is no special post-allocation work necessary for the new copy space.  The call to <tt>super.postAlloc()</tt> should remain conditional on <tt>allocator != Tutorial.ALLOC_DEFAULT</tt>.</li>
	<li>change the check within <tt>getAllocatorFromSpace()</tt> to check against <tt>Tutorial.nurserySpace</tt> and to return <tt>nursery</tt>.</li>
	<li>adjust <tt>collectionPhase</tt>
	<ol>
		<li>replace call to <tt>ms.prepare()</tt> with <tt>nursery.reset()</tt></li>
		<li>remove call to <tt>ms.release()</tt> since there are no actions necessary for the nursery allocator upon release.</li>
	</ol>
	</li>
</ol>



<h5><a name="BuildingaHybridCollector-Addcopyingtothecollector"></a>Add copying to the collector</h5>

<p>In <tt>TutorialCollector</tt> add the capacity for the collector to allocate (copy), since our new hybrid collector will perform copying.</p>

<ol>
	<li>Add local allocators for both large object space and the mature space:
<div class="code panel" style="border-width: 1px;"><div class="codeContent panelContent">
<pre class="code-java">
  <span class="code-keyword">private</span> <span class="code-keyword">final</span> LargeObjectLocal los = <span class="code-keyword">new</span> LargeObjectLocal(Plan.loSpace);
  <span class="code-keyword">private</span> <span class="code-keyword">final</span> MarkSweepLocal mature = <span class="code-keyword">new</span> MarkSweepLocal(Tutorial.msSpace);
</pre>
</div></div></li>
</ol>


<ol>
	<li>Add an <tt>allocCopy()</tt> method that conditionally allocates to the LOS or mature space:
<div class="code panel" style="border-width: 1px;"><div class="codeContent panelContent">
<pre class="code-java">
@Override
<span class="code-keyword">public</span> <span class="code-keyword">final</span> Address allocCopy(ObjectReference original, <span class="code-object">int</span> bytes,
                               <span class="code-object">int</span> align, <span class="code-object">int</span> offset, <span class="code-object">int</span> allocator) {
  <span class="code-keyword">if</span> (allocator == Plan.ALLOC_LOS)
    <span class="code-keyword">return</span> los.alloc(bytes, align, offset);
  <span class="code-keyword">else</span>
    <span class="code-keyword">return</span> mature.alloc(bytes, align, offset);
}
</pre>
</div></div></li>
	<li>Add a <tt>postCopy()</tt> method that conditionally calls LOS or mature space post-copy actions:
<div class="code panel" style="border-width: 1px;"><div class="codeContent panelContent">
<pre class="code-java">
@Override
<span class="code-keyword">public</span> <span class="code-keyword">final</span> void postCopy(ObjectReference object, ObjectReference typeRef,
                           <span class="code-object">int</span> bytes, <span class="code-object">int</span> allocator) {
  <span class="code-keyword">if</span> (allocator == Plan.ALLOC_LOS)
    Plan.loSpace.initializeHeader(object, <span class="code-keyword">false</span>);
  <span class="code-keyword">else</span>
    Tutorial.msSpace.postCopy(object, <span class="code-keyword">true</span>);
}
</pre>
</div></div></li>
</ol>


<h5><a name="BuildingaHybridCollector-Makenecessarychangesto%7B%7BTutorialTraceLocal%7D%7D"></a>Make necessary changes to <tt>TutorialTraceLocal</tt></h5>
<ol>
	<li>Add <tt>nurserySpace</tt> clauses to <tt>isLive()</tt> and <tt>traceObject()</tt>:
	<ol>
		<li>Add the following to <tt>isLive()</tt>:
<div class="code panel" style="border-width: 1px;"><div class="codeContent panelContent">
<pre class="code-java">
<span class="code-keyword">if</span> (Space.isInSpace(Tutorial.NURSERY, object))
  <span class="code-keyword">return</span> Tutorial.nurserySpace.isLive(object);
</pre>
</div></div></li>
		<li>Add the following to <tt>traceObject()</tt>:
<div class="code panel" style="border-width: 1px;"><div class="codeContent panelContent">
<pre class="code-java">
<span class="code-keyword">if</span> (Space.isInSpace(Tutorial.NURSERY, object))
  <span class="code-keyword">return</span> Tutorial.nurserySpace.traceObject(<span class="code-keyword">this</span>, object, Tutorial.ALLOC_DEFAULT);
</pre>
</div></div></li>
	</ol>
	</li>
	<li>Add a new <tt>precopyObject()</tt> method, which is necessary for all copying collectors:
<div class="code panel" style="border-width: 1px;"><div class="codeContent panelContent">
<pre class="code-java">
@Override
<span class="code-keyword">public</span> ObjectReference precopyObject(ObjectReference object) {
  <span class="code-keyword">if</span> (object.isNull()) <span class="code-keyword">return</span> object;
  <span class="code-keyword">else</span> <span class="code-keyword">if</span> (Space.isInSpace(Tutorial.NURSERY, object))
    <span class="code-keyword">return</span> Tutorial.nurserySpace.traceObject(<span class="code-keyword">this</span>, object, Tutorial.ALLOC_DEFAULT);
  <span class="code-keyword">else</span>
    <span class="code-keyword">return</span> object;
}
</pre>
</div></div></li>
	<li>Add a new <tt>willNotMoveInCurrentCollection()</tt> method, which identifies those objects which do not move (necessary for copying collectors):
<div class="code panel" style="border-width: 1px;"><div class="codeContent panelContent">
<pre class="code-java">
@Override
<span class="code-keyword">public</span> <span class="code-object">boolean</span> willNotMoveInCurrentCollection(ObjectReference object) {
  <span class="code-keyword">return</span> !Space.isInSpace(Tutorial.NURSERY, object);
}
</pre>
</div></div></li>
</ol>


<p>With these changes, Tutorial should now work.  You should be able to again build a BaseBaseTutorial image and test it against any benchmark.  Again, if you use <tt>-X:gc:verbose=3</tt> you can see the movement of data among the spaces at each garbage collection.</p>
<div class='panelMacro'><table class='infoMacro'><colgroup><col width='24'><col></colgroup><tr><td valign='top'><img src="images/icons/emoticons/information.gif" width="16" height="16" align="absmiddle" alt="" border="0"></td><td><b>Checkpoint</b><br />This <a href="http://cs.anu.edu.au/people/Steve.Blackburn/misc/mmtk-tutorial/tutorial-04.zip">zip file</a> captures all of the above steps with respect to Jikes RVM 3.0.1.  You can use the archive to verify you've completed the above steps correctly.</td></tr></table></div>

				    
                    			    </td>
		    </tr>
	    </table>
	    <table border="0" cellpadding="0" cellspacing="0" width="100%">
			<tr>
				<td height="12" background="http://docs.codehaus.org/images/border/border_bottom.gif"><img src="images/border/spacer.gif" width="1" height="1" border="0"/></td>
			</tr>
		    <tr>
			    <td align="center"><font color="grey">Document generated by Confluence on Jul 04, 2010 19:57</font></td>
		    </tr>
	    </table>
    </body>
</html>